package main

type ListNode struct {
   Val int
   Next *ListNode
}

var curr = 0

// 删除第 n 个节点，并返回删除节点后的链表的头节点
func removeNth(head *ListNode, n int) *ListNode {
   // 最小子问题
   if head == nil {
      return nil
   }
   curr++
   if curr == n {
      return head.Next
   }
   ret := removeNth(head.Next, n)
   head.Next = ret
   return head
}


// 删除倒数第 n 个节点，并返回删除节点后的链表的头节点
func removeNthFromEnd(head *ListNode, n int) *ListNode {
   // 最小子问题
   if head == nil {
      return nil
   }

   ret := removeNthFromEnd(head.Next, n)
   head.Next = ret

   curr++
   if curr == n {
      return head.Next
   }

   return head
}
